// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 01 背包问题：使用滚动数组进行优化，删除横坐标，从右往左填表
// 完全背包问题：使用滚动数组进行优化，删除横坐标，从左往右填表

// 例题 6:
// 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
//
//        计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
//
//        你可以认为每种硬币的数量是无限的。
//
//        示例 1：
//
//        输入：coins = [1, 2, 5], amount = 11
//        输出：3
//        解释：11 = 5 + 5 + 1
//        示例 2：
//
//        输入：coins = [2], amount = 3
//        输出：-1
//        示例 3：
//
//        输入：coins = [1], amount = 0
//        输出：0
//
//
//        提示：
//
//        1 <= coins.length <= 12
//        1 <= coins[i] <= 231 - 1
//        0 <= amount <= 104

// 解题思路:
// dp[i][j] 表示从 [0, i] 区间内选取硬币，金额正好等于 j 的最小硬币个数
// 初始化：
// dp[0][j] = -1, 1 <= j <= amount
// 根据最后一个硬币分情况讨论：
// 不选 i 位置的硬币: dp[i][j] = dp[i - 1][j]
// 选 i 位置的硬币: dp[i][j] = dp[i][j - coins[i]] + 1
// 选取两种情况下的最小值
// 细节：如果其中一种情况为 -1，表示无法凑出和为 amount 的情况，不参与最小值的选择

public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];

        for(int j = 1; j <= amount; j++){
            dp[0][j] = -1;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1] && dp[i][j - coins[i - 1]] != -1){
                    if(dp[i][j] != -1){
                        dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
                    }else{
                        dp[i][j] = dp[i][j - coins[i - 1]] + 1;
                    }
                }
            }
        }
        return dp[n][amount];
    }
}
